//给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [fromi, toi, we
//ighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权
//值和最小。 
//
// 请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在
//某些最小生成树中但不会出现在所有最小生成树中的边。 
//
// 请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。 
//
// 
//
// 示例 1： 
//
// 
//
// 输入：n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
//输出：[[0,1],[2,3,4,5]]
//解释：上图描述了给定图。
//下图是所有的最小生成树。
//
//注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出的第一个列表。
//边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。
// 
//
// 示例 2 ： 
//
// 
//
// 输入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
//输出：[[],[0,1,2,3]]
//解释：可以观察到 4 条边都有相同的权值，任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。
// 
//
// 
//
// 提示： 
//
// 
// 2 <= n <= 100 
// 1 <= edges.length <= min(200, n * (n - 1) / 2) 
// edges[i].length == 3 
// 0 <= fromi < toi < n 
// 1 <= weighti <= 1000 
// 所有 (fromi, toi) 数对都是互不相同的。 
// 
// Related Topics 深度优先搜索 并查集 
// 👍 49 👎 0
#include <iostream>
#include <vector>

using namespace std;

class Djset {
public:
    vector<int> parent;  // 记录节点的根
    vector<int> rank;
    vector<int> sz;// 记录根节点的深度（用于优化）
    Djset(int n): parent(vector<int>(n)), rank(vector<int>(n)) ,sz(n,1){
        for (int i = 0; i < n; i++) {
            parent[i] = 0;
        }
    }

//    int find(int x) {
//        // 压缩方式：直接指向根节点
//        if (x != parent[x]) {
//            parent[x] = find(parent[x]);
//        }
//        return parent[x];
//    }
    int find(int x){
        return parent[x] == x ? x : find(parent[x]);
    }



//    void merge(int x, int y) {
//        int rootx = find(x);
//        int rooty = find(y);
//        if (rootx != rooty) {
//            if (rank[rootx] < rank[rooty]) {
//                swap(rootx, rooty);
//            }
//            parent[rooty] = rootx;
//            if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
//        }
//    }
    void unite(int x , int y){
        if (sz[x] < sz[y]){
            swap(x,y);
        }
        parent[y] = x;
        sz[x] += sz[y];
    }

    bool findAndUnite(int x,int y){
        int x0 = find(x);
        int y0 = find(y);
        if (x0 != y0){
            unite(x0,y0);
            return true;
        }
        return false;
    }
};

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
        int m = edges.size();
        for (int i = 0; i < m; ++i) {
            edges[i].push_back(i);
        }
        sort(edges.begin(),edges.end(),[](const auto& a,const auto& b){return a[2]<b[2];});

        //计算最小生成树对应的边权之和
        Djset ds(n);
        int value = 0;
        for (int i = 0; i < m; ++i) {
            if (ds.findAndUnite(edges[i][0],edges[i][1])){
                value += edges[i][2];
            }
        }

        vector<vector<int>> res(2);

        //找关键边
        vector<int> label(m);
        for (int i = 0; i < m; ++i) {
            Djset ds1(n);
            int cur_v = 0;
            for (int j = 0; j < m; ++j) {
                if (i == j){
                    continue;
                }
                if (ds.findAndUnite(edges[j][0],edges[j][1])){
                    cur_v += edges[j][2];
                }
            }
            if (cur_v != value){
                label[i] = 1;
                cout<<edges[i][3]<<endl;
                res[0].push_back(edges[i][3]);
            }
        }

        //找伪关键边
        for (int i = 0; i < m; ++i) {

            //不是关键边
            if (label[i]){
                continue;
            }

            Djset ds1(n);
            int cur_v = 0;
            if (ds1.findAndUnite(edges[i][0],edges[i][1])){
                cur_v += edges[i][2];
            }
            for (int j = 0; j < m; ++j) {
                if (i == j){
                    continue;
                }
                if (ds1.findAndUnite(edges[j][0],edges[j][1])){
                    cur_v += edges[j][2];
                }
            }
            if (cur_v == value){
                res[1].push_back(edges[i][3]);
            }
        }
        return res;
    }
};
//leetcode submit region end(Prohibit modification and deletion)
